class Solution {
public:
    //cur指向最左边，也是最小的元素
    //left和right范围在[cur+1,len-1]
    /*当left<right
    num[cur]+num[left]+num[right]<0,让left向右移动，并且跳过与当前num[left]相同的元素
         比如：left++ 但是num[left]==num[left-1];
    num[cur]+num[left]+num[right]>0,让right向左移动，并且跳过与当前num[right]相同的元素
    num[cur]+num[left]+num[right]==0,记录结果，同时让left++ right--
    */
    vector<vector<int> > threeSum(vector<int> &num) {
          vector<vector<int>> res;
        if(num.size() < 3) return res;
        sort(num.begin(), num.end());
        //-2 1 1 2
        for(int i=0; i<num.size(); i++){
            if(num[i] > 0) return res;
            if(i>0 && num[i]== num[i-1]) continue;
            int cur = num[i];
            int left = i+1;
            int right = num.size()-1;
            while(left<right){
                if((cur + num[left] + num[right]) == 0){
                    vector<int> rec;
                    rec.push_back(cur);
                    rec.push_back(num[left]);
                    rec.push_back(num[right]);
                    res.push_back(rec);
                    while(left<right && num[left] == num[left+1]) left++; //跳过相同的
                    while(left<right && num[right] == num[right-1]) right--; //跳过相同的
                    left++;
                    right--;
                }
                else if((cur + num[left] + num[right]) < 0) left++;
                else right--;
                 
            }
        }
        return res;
    }
};